1. Field of the Invention
The present invention relates to information security techniques. More particularly, the present invention relates to a method and a system for authentication whose basis for security resides in the difficulty in solving annihilator determining problems, wherein system users are granted a prover""s function based on secret information while the secret information itself is being hidden.
2. Description of the Related Art
Decryption keys for public key cryptosystems, signature keys for signature systems and authentication keys for authentication systems are all characteristic information that authenticates those who possess these items of secret information.
Described below is a typical authentication method proposed by Guillou and Quisquater in xe2x80x9cA practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memoryxe2x80x9d (Advances in Cryptology EUROCRYPT ""87, C. G. Guenther (ed.), Springer-Verlag, pp. 123-128).
FIG. 1 shows how this authentication method works.
In FIG. 1, it is assumed that n stands for a composite number which is difficult to factorize; G for a multiplicative group (Z/nZ)* of the ring of residue classes of rational integers modulo n; p for a prime number not dividing the Carmichael function xcex(n) of n; Fp for the finite field with p-elements; D for a space of commitments; xcfx80 for a function from G to D; Ixcex5G for public verification information; and xxcex5G for authentication characteristic information satisfying Ixp=1.
Those who possess authentication characteristic information x may carry out the following proverr""s operations:
1. Generate a random number kxcex5G and transmit a commitment r=xcfx80(kp).
2. Transmit a response s=kxc in reply to a given challenge cxcex5Fp.
Any party who knows verification information I can verify the prover""s operations by performing the following verifier""s operations to make sure that the prover indeed possesses the authentication characteristic information:
1. Upon receipt of a commitment r, transmit a randomly generated challenge cxcex5Fp to the prover.
2. Check that the returned response s satisfies r=xcfx80(spIc)
The method above is built on the assumption that those who possess the secret information will keep it undisclosed. Such confidentiality makes it possible to implement encrypted statements that may be decrypted, signatures that may be generated, and authenticating procedures that may be executed, by only those who have the secret information.
The above method may be employed uniquely if those who possess the secret information will suffer disadvantages in case they disclose the information. A typical situation to which the method may apply is one in which secret information, kept by each individual, is the characteristic information that authenticates the individual in question.
In such cases, the characteristic information plays the role of keys to one""s home or one""s seal for official approval. In fact, it is easy to realize such keys or individuals"" seals in the form of digital information as a direct application of the above-described cryptgraphic techniques. Illustratively, the lock to one""s home may be constituted as a verifier according to the Guillou-Quisquater method. The lock of the home is opened only if the verification is successful. In that case, the possession of authentication characteristic information x is exactly equivalent to the custody of the key to one""s home.
In contrast to the situation above where disclosure of authentication characteristic information harms the individual""s interests as is the case with the key to one""s home, there are circumstances in which the disclosure of the information can benefit the individual. The latter situation involves individuals possessing characteristic information that grants them rights or qualifications to receive specific services.
In such cases, unlike the earlier situation where individuals use characteristic information to authenticate themselves, the characteristic information for granting rights or qualifications cannot be distributed to those who are entitled to such privileges, the distributed information being putatively used to verify the possession of the characteristic information. Because the disclosure of characteristic information does not harm the interests of those who possess the information, they can wrongly pass it on to third parties from whom they may receive rewards in return.
Under these circumstances, conventional public key cryptosystems do not simply utilize the above-described public key cryptgraphy techniques for authentication. Instead, the techniques have been practiced in the form of three typical methods:
(1) A first conventional method involves individuals possessing secret characteristic information that is due them, while a verifier for verifying whether any individual has specific rights or qualifications retains information about the individuals and the secret characteristic information owned by the individuals. According to this method, disclosure of the characteristic information harms individuals"" interests. As such, the method is suitable for authenticating rights and qualifications granted to individuals.
(2) A second conventional method involves individuals possessing secret characteristic information that is due to them, while a verifier for verifying whether any individual has specific rights or qualifications retains public information about the individuals as well as public information corresponding to the secret characteristic information owned by the individuals. According to this method, disclosure of the characteristic information also harms individuals"" interests. As such, the method is also suitable for authenticating rights and qualifications granted to individuals.
(3) A third conventional method works as follows: a party that grants rights or qualifications furnishes each of the recipients of these rights or qualifications with a signature generated by use of characteristic information owned by the privilege-granting party. A verifier verifies the signature to authenticate the demanded rights or qualifications. An example of this method is discussed by D. Chaum in xe2x80x9cOnline Cash Checksxe2x80x9d (Advances in Cryptology EUROCRYPT ""89, J. J. Quisquater, J. Vandewalle (ed.), Springer-Verlag, pp. 288-293).
This method is free from problems associated with leaks of characteristic information because those who are to prove the possession of the rights or qualifications do not retain the characteristic information.
The first conventional method above requires the verifier to retain a list of those who possess the rights or qualifications granted to them. The requirement poses a storing and administrative burden on the verifier and necessitates provision of a high-performance verification device. Because the verifying device cannot be made independently of those who grant the specific rights or qualifications, constant exchanges of information are required between the verification device and the privilege-granting party.
Since the verifier retains individuals"" characteristic information, the individuals to be authenticated by this method are vulnerable to wrongful leaks of such characteristic information.
The second characteristic method above also requires the verifier to retain a list of those who possess the rights or qualifications granted to them. The requirement poses a storing and administrative burden on the verifier and necessitates provision of a high-performance verification device. Likewise, because the verifying device cannot be made independently of those who grant the specific rights or qualifications, constant exchanges of information are required between the verification device and the privilege-granting party.
Where the third conventional method above is in use, distributed signature information may be used by anyone. This requires that the signature be protected against duplication. The requirement is met by preventing double use of each signature value. Specifically, all signature values, once used, are stored by the verifier so that the latter will make sure that any signature value is used only once. For the verifier to implement this function requires installing a high-performance verification device. In addition, constant exchanges of information are needed between verification devices so that the devices may share a list of once-used signature values.
As outlined, the three convention methods above are all subject to serious disadvantages. In particular, it is difficult for the verifier to implement verification devices or programs on a limited scale.
By contrast, the authentication method mentioned earlier and based on characteristic information indicating granted rights or qualifications is more advantageous. According to this method, verification only requires authenticating the possession of such characteristic information.
As described, the conventional techniques are vulnerable to leaks of authentication characteristic information to a third party if the verification device for authenticating rights or qualifications is limited in scale. To eliminate the risk of such leaks requires building a large-scale verification device.
It is therefore an object of the present invention to provide a method and a system for authentication implemented in the form of a small-scale verification device for preventing leaks of authentication characteristic information to a third party upon authentication of rights or qualifications.
In carrying out the present invention and according to one aspect thereof, there are provided a method and a system for authentication making use of:
1. an interactive device for generating document secret information based on a document, i.e., information which can be made public and which is determined upon issuance of a ticket, the interactive device interacting with a prover for authentication on the basis of the generated document secret information; and
2. a ticket which is generated from the document secret information and authentication characteristic information and which constitutes information that can be made public.
The workings of the present invention are outlined below in preparation for subsequent descriptions of embodiments.
FIG. 2 is a schematic view showing an overall constitution of an authentication system embodying the present invention.
In FIG. 2, a ticket issuing party 400 issues interactive devices 300 and distributes them to users, each device being characterized by its unique secret function. If the secret function characterizing a given interactive device 300 were known to a user, the interactive device 300 would be copied freely leading to the abusive issue of tickets that cannot be controlled by the ticket issuing party. To prevent such misuse requires protecting the secret function of each interactive device 300 against theftxe2x80x94even by its legitimate owner. The interactive device 300 may be implemented illustratively as a so-called smart card (IC card).
Initially, data m called a document is input to an interactive device 300. In turn, document secret information is generated by use of a secret function f unique to the interactive device 300 in question. The interactive device 300 then interacts with a prover 200 in accordance with the document secret information.
More specifically, the interaction proceeds in the following sequence:
1. Output commitment r.
2. Input challenge c.
3. Output response "sgr".
The interaction above is basically the same in format as the interaction carried out by the prover with the verifier under the Guillou-Quisquater authentication method mentioned earlier, the latter method being illustrated in FIG. 1.
Documents are not limited to being used for generating document secret information. Documents can also constitute programs or commands that may be executed by the interactive device 300, or can be parameters of processes that may be carried out by the interactive device 300.
When issuing tickets t each corresponding to authentication characteristic information x, the ticket issuing party does so by distributing to users a function for generating an interaction (r, c, s) based on the authentication characteristic information x, as follows:
The ticket issuing party first uses the ticket issuing device 400 to calculate document secret information xcexc based on a secret function f of the interactive device 300 owned by each user and on a document m to be transmitted to the interactive device 300 upon generation of an interaction. A ticket t generated from the authentication characteristic information x and the document secret information xcexc is issued to the user in question.
The authentication characteristic information x and the document secret information are not disclosed to the user.
In turn, the user inputs the designated document m to the interactive device 300 to generate an interaction (r, c, "sgr"). Using the issued ticket, the user converts the interaction (r, c, "sgr") into the interaction (r, c, s) based on the authentication characteristic information corresponding to the ticket.
If process instructions are described in the document for the interactive device 300, the generation of the interaction by use of the ticket is associated with the instructions written in the document. The instructions can then be used to condition the effectiveness of the ticket.
Specifically, the conversion of the interaction is made possible by calculating a response s based on the challenge c, response "sgr" and ticket t.
The interaction (r, c, s) thus converted is exactly that which is generated by the prover adopting the Guillou-Quisquater authentication method of FIG. 1. This will be discussed in the ensuing description of embodiments.
The authentication characteristic information x corresponding to each ticket is generated independently of the document secret information that varies from one document to another for individual interactive devices 300.
The ticket issuing party may thus distribute to users the interactive function based on desired authentication characteristic information x in the form of tickets associated with desired documents. The distribution of the function is accomplished without disclosure of the authentication characteristic information.
Other objects, features and advantages of the present invention will become more apparent upon a reading of the following description and appended drawings.